#include "sd_syncblist.h"
#include "sd_memory.h"

static sd_SyncBlistNode* CreateNode(sd_SyncBlist* blist)
{
	sd_SyncBlistNode* newnode;
	sd_MemoryAllocator* ma = blist->ma;
	SD_ASSERT(ma != NULL);
	newnode = (sd_SyncBlistNode*)ma->allocate(sizeof(sd_SyncBlistNode)+blist->node_cap*blist->elemsize-1);
	if (newnode == NULL)
	{
		SD_ASSERT(false);
		return NULL;
	}
	newnode->blist = blist;
	newnode->next = NULL;
	newnode->usedcount = 0;
	newnode->capacity = blist->node_cap;
	sd_RWLock_Init(&newnode->lock);
	return newnode;
}

static sd_SyncBlistNode* LockPredecessor(sd_SyncBlist* blist, sd_SyncBlistNode* node)
{
	sd_SyncBlistNode* prenode;

	SD_ASSERT(node != NULL);

	/* If this node is the first node, so it has no predecessor */
	if (node == blist->firstNode)
	{
		return NULL;
	}
	prenode = blist->firstNode;
	sd_RWLock_WLock(&prenode->lock);
	
	while(prenode != NULL)
	{
		if (prenode->next == node)
			return prenode;
		sd_RWLock_WLock(&prenode->next->lock);
		sd_RWLock_Unlock(&prenode->lock);
		prenode = prenode->next;
	}
	/* Not found */
	return NULL; 
}

static sd_Ret RemoveNode(sd_SyncBlist* blist, sd_SyncBlistNode* node)
{
	sd_MemoryAllocator* ma = blist->ma;
	SD_ASSERT(node != NULL && ma != NULL);

	/* The first node this blist is reserved, only other nodes can be removed */
	if (node != blist->firstNode)
	{
		sd_SyncBlistNode* prenode = LockPredecessor(blist, node);
		SD_ASSERT(prenode != NULL);
		
		sd_RWLock_WLock(&node->lock);
		
		/* Only empty node can be removed */
		if (node->usedcount != 0)
		{
			sd_RWLock_Unlock(&node->lock);
			sd_RWLock_Unlock(&prenode->lock);
			return SD_RET_OK;
		}

		prenode->next = node->next;

		/* Free this node */
		sd_RWLock_Unlock(&node->lock);
		sd_RWLock_Destroy(&node->lock);
		ma->deallocate(node);

		sd_RWLock_Unlock(&prenode->lock);
	}
	return SD_RET_OK;
}


sd_Ret sd_SyncBlistCreate(sd_SyncBlist* blist, size_t elemsize, size_t node_cap, struct sd_MemoryAllocator* ma)
{
	blist->ma = ma;
	blist->elemsize = elemsize;
	blist->node_cap = node_cap;
	if (blist->ma == NULL)
		blist->ma = sd_GetDefaultMemoryAllocator();
	/* Create the first node */
	blist->firstNode = CreateNode(blist); 
	return SD_RET_OK;
}

sd_Ret sd_SyncBlistFree(sd_SyncBlist* blist)
{
	sd_MemoryAllocator* ma = blist->ma;
	sd_SyncBlistNode* node = blist->firstNode;
	sd_SyncBlistNode* nextnode;
	while(node != NULL)
	{
		nextnode = node->next;
		sd_RWLock_Destroy(&node->lock);
		ma->deallocate(node);
		node = nextnode;
	}
	return SD_RET_OK;
}

sd_Ret sd_SyncBlistInsert(sd_SyncBlist* blist, const void* elem)
{
	size_t curcount;
	sd_SyncBlistNode* node;
	node = blist->firstNode;
	sd_RWLock_WLock(&node->lock);
	
	while(node->usedcount == node->capacity)
	{
		if (node->next == NULL)
		{
			sd_SyncBlistNode* newnode = CreateNode(blist);
			node->next = newnode;
		}
		sd_RWLock_WLock(&node->next->lock);
		sd_RWLock_Unlock(&node->lock);
		node = node->next;
	}
	curcount = node->usedcount;
	memcpy(&node->buf[curcount*blist->elemsize], elem, blist->elemsize);
	node->usedcount++;
	
	/* If the last node is full, create another node */
	if (node->next == NULL && node->usedcount == node->capacity)
	{
		sd_SyncBlistNode* newnode = CreateNode(blist);
		node->next = newnode;
	}
	sd_RWLock_Unlock(&node->lock);
	
	return SD_RET_OK;
}

sd_Ret sd_SyncBlistInsertTogether(sd_SyncBlist* blist, const void* elem1, size_t elem1size, const void* elem2)
{
	size_t curcount;
	sd_SyncBlistNode* node;
	node = blist->firstNode;
	sd_RWLock_WLock(&node->lock);
	
	while(node->usedcount == node->capacity)
	{
		if (node->next == NULL)
		{
			sd_SyncBlistNode* newnode = CreateNode(blist);
			node->next = newnode;
		}
		sd_RWLock_WLock(&node->next->lock);
		sd_RWLock_Unlock(&node->lock);
		node = node->next;
	}
	curcount = node->usedcount;
	memcpy(&node->buf[curcount*blist->elemsize], elem1, elem1size);
	memcpy(&node->buf[curcount*blist->elemsize+elem1size], elem2, blist->elemsize-elem1size);
	node->usedcount++;

	/* If the last node is full, create another node */
	if (node->next == NULL && node->usedcount == node->capacity)
	{
		sd_SyncBlistNode* newnode = CreateNode(blist);
		node->next = newnode;
	}
	sd_RWLock_Unlock(&node->lock);

	return SD_RET_OK;
}

sd_Ret sd_SyncBlistInsertTogetherWithoutLock(sd_SyncBlist* blist, const void* elem1, size_t elem1size, const void* elem2)
{
	size_t curcount;
	sd_SyncBlistNode* node;
	node = blist->firstNode;
	
	while(node->usedcount == node->capacity)
	{
		if (node->next == NULL)
		{
			sd_SyncBlistNode* newnode = CreateNode(blist);
			node->next = newnode;
		}
		node = node->next;
	}
	curcount = node->usedcount;
	memcpy(&node->buf[curcount*blist->elemsize], elem1, elem1size);
	memcpy(&node->buf[curcount*blist->elemsize+elem1size], elem2, blist->elemsize-elem1size);
	node->usedcount++;

	/* If the last node is full, create another node */
	if (node->next == NULL && node->usedcount == node->capacity)
	{
		sd_SyncBlistNode* newnode = CreateNode(blist);
		node->next = newnode;
	}

	return SD_RET_OK;
}

sd_Ret sd_SyncBlistEmpty(sd_SyncBlist* blist)
{
	sd_Ret ret;
	sd_SyncBlistNode* node = NULL;
	node = blist->firstNode;
	sd_RWLock_RLock(&node->lock);
	if (node->next != NULL || node->usedcount > 0)
		ret = SD_RET_FALSE;
	else
		ret = SD_RET_TRUE;
	sd_RWLock_Unlock(&node->lock);
	return ret;
}

sd_Ret sd_SyncBlistBegin(sd_SyncBlist* blist, sd_SyncBlistIterator* iter, bool bWLock, bool bLockList)
{
	iter->blist = blist;
	iter->curnode = blist->firstNode;
	if (bWLock)
		sd_RWLock_WLock(&iter->curnode->lock);
	else
		sd_RWLock_RLock(&iter->curnode->lock);
	iter->curindexInNode = -1;
	iter->bWLock = bWLock;
	iter->bCurrentNodeLocked = true;
	iter->bLockList = bLockList;
	return SD_RET_OK;
}

sd_Ret sd_SyncBlistNext(sd_SyncBlistIterator* iter)
{
	if (iter->curindexInNode == -1)
	{
		iter->curindexInNode = 0;
		iter->bCurrentNodeLocked = true;
	}
	else
		iter->curindexInNode++;
	
	while (iter->curindexInNode >= (int)iter->curnode->usedcount)
	{
		if (iter->curnode->next == NULL)
		{
			/* No more node to iterate*/
			return SD_RET_FALSE;
		}
		else
		{
			/* Jump to the next node */
			if (iter->bWLock)
				sd_RWLock_WLock(&(iter->curnode->next->lock));
			else
				sd_RWLock_RLock(&(iter->curnode->next->lock));
			
			if (iter->bLockList)
			{
				if (iter->curnode != iter->blist->firstNode)
					sd_RWLock_Unlock(&iter->curnode->lock);
			}
			else
			{
				if (iter->curnode !=NULL)
					sd_RWLock_Unlock(&iter->curnode->lock);
			}

			iter->curnode = iter->curnode->next;
			iter->curindexInNode = 0;
		}
	}
	return SD_RET_TRUE;
}

sd_Ret sd_SyncBlistGet(sd_SyncBlistIterator* iter, void* elem)
{
	size_t elemsize = iter->blist->elemsize;	
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (elem != NULL)
	{
		int idx = iter->curindexInNode;
		sd_SyncBlistNode* curnode = iter->curnode;
		memcpy(elem, &(curnode->buf[idx*elemsize]), elemsize);
	}
	return SD_RET_TRUE;
}

sd_Ret sd_SyncBlistPartialGet(sd_SyncBlistIterator* iter, void* key, int offset, size_t size)
{
	size_t elemsize = iter->blist->elemsize;		
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (key != NULL)
	{
		int idx = iter->curindexInNode;
		sd_SyncBlistNode* curnode = iter->curnode;
		memcpy(key, &(curnode->buf[idx*elemsize+offset]), size);
	}
	return SD_RET_TRUE;
}

sd_Ret sd_SyncBlistReleaseLock(sd_SyncBlistIterator* iter)
{
	if (iter->bCurrentNodeLocked)
	{
		sd_RWLock_Unlock(&iter->curnode->lock);
		iter->bCurrentNodeLocked = false;
	}
	if (iter->bLockList)
	{
		if (iter->blist->firstNode != iter->curnode)
			sd_RWLock_Unlock(&iter->blist->firstNode->lock);
		iter->bLockList = false;
	}
	return SD_RET_OK;
}


sd_Ret sd_SyncBlistRemoveAndReleaseLock(sd_SyncBlistIterator* iter)
{
	sd_Ret ret;
	sd_SyncBlistNode* curnode = iter->curnode;
	int idx = iter->curindexInNode;
	size_t movcount = (size_t)(curnode->usedcount - idx - 1);
	if (movcount > 0)
	{
		size_t elemsize = iter->blist->elemsize;
		memmove(&curnode->buf[idx*elemsize], &curnode->buf[(idx+1)*elemsize], movcount*elemsize);
	}
	curnode->usedcount--;

	if (curnode->usedcount == 0)
	{
		/* Before removing this node, we must release the lock of this node */
		sd_RWLock_Unlock(&curnode->lock);
		iter->bCurrentNodeLocked = false;
		if (iter->bLockList)
		{
			if (iter->blist->firstNode != iter->curnode)
				sd_RWLock_Unlock(&iter->blist->firstNode->lock);
			iter->bLockList = false;
		}

		/* Remove the whole node */
		ret = RemoveNode(iter->blist, curnode);
		SD_ON_FAILED_RETURN(ret);
		
	}
	else
	{
		sd_RWLock_Unlock(&curnode->lock);
		iter->bCurrentNodeLocked = false;
		if (iter->bLockList)
		{
			if (iter->blist->firstNode != iter->curnode)
				sd_RWLock_Unlock(&iter->blist->firstNode->lock);
			iter->bLockList = false;
		}
	}
	
	return SD_RET_OK;
}

sd_Ret sd_SyncBlistClear(sd_SyncBlist* blist)
{
	sd_SyncBlistNode* node;
	sd_SyncBlistNode* tempNode;
	/* Only maintain the first node */
	node = blist->firstNode->next;
	sd_RWLock_WLock(&node->lock);
	while(node != NULL)
	{
		tempNode = node;
		node = node->next;
		if (node)
			sd_RWLock_WLock(&node->lock);
		sd_RWLock_Unlock(&tempNode->lock);
		sd_RWLock_Destroy(&tempNode->lock);
		blist->ma->deallocate(tempNode);
	}
	blist->firstNode->usedcount = 0;
	blist->firstNode->next = NULL;
	return SD_RET_OK;
}

sd_Ret sd_SyncBlistUpdate(sd_SyncBlistIterator* iter, const void* elem)
{
	size_t elemsize = iter->blist->elemsize;
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (elem != NULL)
	{
		int idx = iter->curindexInNode;
		sd_SyncBlistNode* curnode = iter->curnode;
		memcpy(&(curnode->buf[idx*elemsize]),elem , elemsize);
	}
	return SD_RET_TRUE;
}

sd_Ret sd_SyncBlistUpdateTogether(sd_SyncBlistIterator* iter, const void* elem1, size_t elem1size, const void* elem2)
{
	size_t elemsize = iter->blist->elemsize;
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (elem1 != NULL)
	{
		int idx = iter->curindexInNode;
		sd_SyncBlistNode* curnode = iter->curnode;
		memcpy(&(curnode->buf[idx*elemsize]),elem1, elem1size);
		memcpy(&(curnode->buf[idx*elemsize+elem1size]),elem2, elemsize-elem1size);
	}
	return SD_RET_TRUE;

}


